/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    if (n === 1) return [['Q']]
    let result = []
    function recursion(arr, count) {
        if (arr.length === n) {
            let list = arr.map(item=>{
                return item.join('')
            })
            result.push(list)
        }

        for (let idx = 0; idx < n; idx++) {
            let curRow = new Array(n).fill('.')
            curRow[idx] = 'Q'

            let flag = true

            for (let i = 0; i < arr.length; i++) {
                const val = arr[i];
                // 现在判断同列的棋盘上面有没有Q
                if (val[idx] === 'Q') {
                    flag = false
                }
                // // 现在判断45%和135%的棋盘上面有没有Q
                if (val[idx + (count - i)] === 'Q' || val[idx - (count - i)] === 'Q') {
                    flag = false
                }
            }

            if (flag) {
                arr.push(curRow)
                recursion(arr, count + 1)
                arr.pop()
            }


        }
    }

    recursion([], 0)
    return result

};
solveNQueens(4)
//       count   位置
// "Q...", 0  
// "..Q.", 1  
// "...Q", 2     3
// ".Q.."

// [["Q...","..Q.","...Q",".Q.."],["Q...","...Q",".Q..","..Q."],[".Q..","...Q","Q...","..Q."],["..Q.","Q...",".Q..","...Q"]]